package sort;

/**
 * @author way
 * @create 2025-03-17 21:11
 */
public class MergeSort {
    void merge(int[] a, int lo, int mid, int hi) {
        int[] aux = new int[a.length];//辅助数组
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; ++k) {
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; ++k) {
            if (i > mid)              a[k] = aux[j++];
            else if (j > hi)          a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else                      a[k] = aux[i++];
        }
    }

    void mergeSort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, 0, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 3, 8, 2, 7, 9, 1};
        MergeSort sort = new MergeSort();
        sort.mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
